import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Leetcode46 {
    public static void main(String[] args) {

        System.out.println(permute(new int[]{1}));
    }

    public static List<List<Integer>> permute(int[] nums) {
        if (nums.length == 1) {
            List<Integer> list = new ArrayList<>();
            Arrays.stream(nums).forEach(list::add);

            return List.of(list);
        }

        List<List<Integer>> previous = permute(subArray(nums, 0, nums.length - 1));

        List<List<Integer>> res = new ArrayList<>();
        int next = nums[nums.length - 1];
        for (List<Integer> list : previous) {
            for (int i = 0; i <= list.size(); i++) {
                List<Integer> cp = new ArrayList<>(list);
                cp.add(i, next);
                res.add(cp);
            }
        }

        return res;
    }

    private static int[] subArray(int[] k, int fromIndex, int toIndex) {
        int[] res = new int[toIndex - fromIndex];

        System.arraycopy(k, fromIndex, res, 0, toIndex - fromIndex);

        return res;
    }
}

